// S-Expression data structure and simple parser
// Copyright 2004 (C) Ralph Thomas

#include <util/sexpression.h>
#include <vector>
#include <ctype.h>

namespace util {
	class sexpressionImpl : public sexpression {
	  private:
		typedef std::vector<sexpression*> sexpList;
		util::string _sval;
		int _ival;
		type _type;
		sexpList _children;

		class childIteratorImpl : public childIterator {
		  private:
			sexpList::const_iterator _i;
			sexpList::const_iterator _end;
		  public:
			childIteratorImpl( sexpList::const_iterator it, sexpList::const_iterator end ) : _i( it ), _end( end ) {}
			
			virtual ~childIteratorImpl() {}

			virtual const sexpression* borrowNextChild() {
				if( _i != _end ) return *_i++;
				return NULL;
			}
		};

	  public:
		sexpressionImpl() : _ival( 0 ), _type( kTypeNil ) {}
		
		virtual ~sexpressionImpl() {
			std::vector<sexpression*>::iterator i;

			for( i = _children.begin(); i != _children.end(); i++ )
				delete *i;
		}

		static sexpressionImpl* fromString( util::string str ) {
			sexpressionImpl* s = new sexpressionImpl;
			s->_sval = str; s->_type = kTypeString;
			return s;
		}

		static sexpressionImpl* fromInt( int i ) {
			sexpressionImpl* s = new sexpressionImpl;
			s->_ival = i; s->_type = kTypeInt;
			return s;
		}

		void adoptChild( sexpression* child ) {
			_type = kTypeParent;
			_children.push_back( child );
		}

		virtual childIterator* getChildIterator() const {
			if( _type == kTypeParent ) return new childIteratorImpl( _children.begin(), _children.end() );
			return NULL;
		}

		virtual type getType() const {
			return _type;
		}

		virtual util::string getString() const {
			if( _type == kTypeString ) return _sval;
			return "";
		}

		virtual int getInt() const {
			if( _type == kTypeInt ) return _ival;
			return 0;
		}
	};

	//
	// mini exception class
	//
	/// This class is used internally by the parser when it encounters an
	/// error.
	//
	class miniException {
	  private:
		util::string _what;
		unsigned int _code;
	  public:
		//
		// miniException( util::string what, unsigned int code )
		//
		/// Create a mini-exception with an explanation of "what".
		///
		/// \param	what	the reason why the exception was thrown
		/// \param	code	the error code to return.
		//
		miniException( util::string what, unsigned int code ) : _what( what ), _code( code ) {}
		//
		// util::string getWhat()
		//
		/// Return the reason why the exception was thrown.
		///
		/// \return	the reason why the exception was thrown.
		//
		util::string getWhat() const { return _what; }
		//
		// unsigned int getCode()
		//
		/// Return the error code describing what went wrong.
		///
		/// \return	one of the sexpression::errorCodes values.
		//
		unsigned int getCode() const { return _code; }
	};

	//
	// sexpression parser
	//
	// this works like this:
	// - if we find a lparen "(" then we call _sexpChildren()
	// - if we find anything else then we call _sexpSimple()
	//
	// we do the tokenization and figuring out where the beginning and
	// end of things are and such.
	//
	sexpression* _sexpSimple( util::string sexp ) {
		if( sexp.empty() ) return NULL;
		if( sexp == "NIL" ) return new sexpressionImpl();
		if( sexp[0] == '\"' ) return sexpressionImpl::fromString( sexp.substr( 1, sexp.size() - 2 ) );
		return sexpressionImpl::fromInt( strtol( sexp.c_str(), NULL, 10 ) );
	}

	sexpression* _sexpChildren( util::string& sexp, unsigned int& error ) {
		//
		// this is how to do it:
		//
		// - tokenize!
		//   - if we find a string int or nil, add it as a child to the
		//     current sexpression
		//   - if we find an lparen then we make a new sexpression, add
		//     it as a child to the current one and then make it the
		//     current one (imagine a stack called "current one")
		//   - if we find an rparen then we pop something off the top
		//     of our current stack.
		//
		util::string::iterator i = sexp.begin();
		util::string token;
		std::vector<sexpressionImpl*> current;
		bool inQuotes = false; // are we inside a quoted expression

		//
		// we basically have to find an lparen to start work.
		//
		try { i = sexp.begin(); while( i != sexp.end() ) {
			i = sexp.begin();
			if( inQuotes ) {
				//
				// while we're inside quotes we add anything
				// to the current token.
				//
				token += *i;
				//
				// has our token been terminated by a double
				// quote mark?
				//
				if( *i == '\"' ) inQuotes = false;
				sexp.erase( i );
				continue;
			} /*else if( (isalnum( *i ) != 0) || (*i == '_') || (*i == '<') || (*i == '>') || (*i == '%') ) {
				//
				// we have a character which belongs in a token
				//
				token += *i;
				sexp.erase( i );
				continue;
			} */else if( *i == '\"' ) {
				//
				// we have encountered the beginning of a
				// quoted expression. it is considered an error
				// if there's anything already in the token
				// variable - that means that somebody put a
				// double quote inside another token. Duh.
				//
				if( !token.empty() ) {
					util::string error = "sexpression.c++ - encountered unexpected double quotes (\") inside other token - text leading up to this error was: ";
					error += token + "\"";
					throw miniException( error, sexpression::kUnexpectedQuotes );
				}
				//
				// looks like we're okay, go into quotes mode
				// which means that we put everything we find
				// into the token variable until we hit another
				// double quotes character.
				//
				inQuotes = true;
				token += *i;
				sexp.erase( i );
				continue;
			} else if( (*i == '{') || (*i == '}') ) {
				//
				// we're in some extension of the IMAP
				// s-expression, which only Cyrus-IMAP
				// seems to use.
				//
				// XXX: I think that these parens only
				// XXX: ever contain a single number.
				//
				sexp.erase( i );
				continue;
			} else if( (*i != '(') && (*i != ')') && !isspace( *i ) ) {
				//
				// This isn't one of those special characters
				// handled below, this is just a character for
				// the current token.
				//
				token += *i;
				sexp.erase( i );
				continue;
			}
			//
			// we have a character which doesn't go into a token,
			// it should either be a space (which means that we
			// might have reached the end of a token, and that we
			// should add it as a child to the current sexpression),
			// or it will be parentheses - an open paren means we
			// should make a new sexpression and make it current,
			// a close paren means we should pop the current
			// sexpression off the top.
			//
			if( !token.empty() ) {
				//
				// check that the current input is valid
				//
				if( (!isspace( *i )) && (*i != ')') && (*i != '(') ) {
					util::string error = "sexpression.c++ - next character invalid: ";
					error += *i;
					error += " remaining string: \"" + sexp + "\"";
					throw miniException( error, sexpression::kInvalidChar );
				}

				//
				// we have a token, and a character which isn't
				// part of the token; lets try to add the token
				// to our list.
				//
				sexpression* sexprToken = _sexpSimple( token );
				if( !sexprToken ) {
					//
					// looks like our token was junk; we can
					// recover from this error, but for now
					// we throw an exception because it's
					// better for debugging the code.
					//
					util::string error = "sexpression.c++ - could not generate simple sexpression out of token, token was: ";
					throw miniException( error + token, sexpression::kInvalidToken );
				}
				if( current.empty() ) {
					//
					// doh - there's no current sexpression
					// to be the parent of this one. we just
					// return this one.
					//
					return sexprToken;
				}
				//
				// we're okay to add this token as a child of
				// the current sexpression, woohoo!
				//
				(*current.rbegin())->adoptChild( sexprToken );
				token = "";
			} 
			if( *i == '(' ) {
				//
				// lparen - we need to make a new sexpression,
				//  add it as a child of the current sexpression
				//  and make it current by adding it to the end
				//  of the "current" vector and incrementing the
				//  parenCount.
				//
				sexpressionImpl* nC = new sexpressionImpl();
				if( !current.empty() )
					(*current.rbegin())->adoptChild( nC );
				current.push_back( nC );
				sexp.erase( i );
				continue;
			} else if( *i == ')' ) {
				//
				// rparen - we need to pop the current
				//  sexpression off and decrement the
				//  parenCount.
				//
				if( current.empty() )
					throw miniException( "sexpression.c++ - unbalanced parentheses, too many close paren", sexpression::kUnbalancedParens );

				if( current.size() == 1 ) {
					sexp.erase( i );
					error = sexpression::kOk;
					return current[0];
				}

				current.pop_back();
				sexp.erase( i );
				continue;
			} 
			sexp.erase( i );
		} } catch ( miniException& m ) {
			//
			// something went wrong while parsing, print out the
			// reason and delete the root sexpression (which will
			// delete all of it's children). Finally return NULL.
			//
			if( !current.empty() ) delete current[0];
			error = m.getCode();
			return NULL;
		}
		//
		// there were not enough close parens. We should set the error
		// and return NULL, as it could be an indication of a bug in
		// this parser (and it's better to return NULL than to return
		// something which might be incorrect).
		//
		if( !current.empty() ) delete current[0];
		error = sexpression::kUnbalancedParens;
		return NULL;
	}

	// empty vtable entries
	sexpression::~sexpression() {}
	sexpression::childIterator::~childIterator() {}
	
	sexpression* sexpression::fromString( util::string sexpr, unsigned int& ecode ) {
		return _sexpChildren( sexpr, ecode );
	}

	sexpression* sexpression::fromStringModify( util::string& sexpr, unsigned int& ecode ) {
		//
		// We only want to modify the string in the event of a
		// correct parse.
		//
		util::string tmp = sexpr;
		sexpression* s = _sexpChildren( tmp, ecode );
		if( s ) sexpr = tmp;
		return s;
	}

};

